package com.wkr.leetcode;

import java.util.*;

public class Solution {


    private String str = "%d = %d + %d";

    /**
     * 给定一个无重复元素的数组 candidates 和一个目标数 target
     * 找出 candidates 中所有可以使数字和为 target 的组合
     * 输入：candidates = [2,3,6,7], target = 7,
     * 所求解集为：
     * [
     * [7],
     * [2,2,3]
     * ]
     * 输入：candidates = [2,3,5], target = 8,
     * 所求解集为：
     * [
     * [2,2,2,2],
     * [2,3,3],
     * [3,5]
     * ]
     *
     *
     * 回溯算法
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        List<Integer> unConfirm = new ArrayList<>();
        dfs(target, candidates, 0, ans, unConfirm);
        return ans;
    }

    public void dfs(int target, int[] candidates, int start, List<List<Integer>> ans, List<Integer> unConfirm) {
        if (target == 0) {
            ans.add(new ArrayList<>(unConfirm));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            System.out.println("未添加前：" + unConfirm.toString());
            unConfirm.add(candidates[i]);
            System.out.println("已添加后：" + unConfirm.toString());

            dfs(target - candidates[i], candidates, i, ans, unConfirm);

            unConfirm.remove(unConfirm.size() - 1);
            System.out.println("已删除后：" + unConfirm.toString());
            System.out.println("over, i = " + i);
        }
    }


    /**
     * 输入：coins = [1, 2, 5], amount = 11
     * 输出：3
     * 解释：11 = 5 + 5 + 1
     *
     * 兑换硬币,求最少需要几个硬币
     * 动态规划
     * 1.确定状态，分解出子问题，例如要求11元最少硬币组合，就可以分解成11-a(k)，最后一枚肯定是1，2，5中的一个
     * 2.转移方程，f[x] = min{f[x - 1] + 1, f[x - 2] + 1, f[x - 5] + 1}
     * 3.初始条件以及边界情况，如0的情况，怎么停止
     * 4.计算顺序
     */
    public int coinChange(int[] coins, int amount) {

        int[] ans = new int[amount + 1];
        ans[0] = 0;
        for (int i = 1; i <= amount; i++) {
            ans[i] = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i - coin >= 0 && ans[i - coin] != Integer.MAX_VALUE) {
                    // 1表示当前硬币
                    ans[i] = Math.min(ans[i - coin] + 1, ans[i]);
                }
            }
        }
        if (ans[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return ans[amount];
    }

    /**
     * 返回最少硬币的组合
     */
    @SuppressWarnings("unchecked")
    public List coinChange2(int[] coins, int amount) {
        List[] combo = new List[amount + 1];
        combo[0] = new ArrayList();
        int[] ans = new int[amount + 1];
        ans[0] = 0;
        for (int i = 1; i <= amount; i++) {
            combo[i] = new ArrayList();
            ans[i] = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i - coin >= 0 && ans[i - coin] != Integer.MAX_VALUE) {
                    if (ans[i - coin] + 1 < ans[i]) {
                        combo[i].clear();
                        ans[i] = ans[i - coin] + 1;
                        combo[i].addAll(combo[i - coin]);
                        combo[i].add(coin);
                    }
                }

            }
        }
        return combo[amount];
    }

    public void dffs(int[] coins, int targrt, int begin, List<List<Integer>> ans, List<Integer> temp) {
        if (targrt == 0) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = begin; i < coins.length; i++) {
            if (targrt - coins[i] < 0) {
                break;
            }
            temp.add(coins[i]);

            dffs(coins, targrt - coins[i], i, ans, temp);

            temp.remove(temp.size() - 1);
        }
    }


    /**
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     * 问总共有多少条不同的路径？
     */
    public int uniquePaths(int m, int n) {
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++) {
            ans[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            ans[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
            }
        }
        return ans[m - 1][n - 1];
    }


    /**
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] ans = new int[m][n];
        ans[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            ans[0][i] = ans[0][i - 1] + grid[0][i];
        }

        for (int j = 1; j < m; j++) {
            ans[j][0] = ans[j - 1][0] + grid[j][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                ans[i][j] = Math.min(ans[i - 1][j], ans[i][j - 1]) + grid[i][j];
            }
        }
        return ans[m - 1][n - 1];
    }


    /**
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> temp = new ArrayList<>();
        threeSumDfs(0, ans, nums, temp);
        return new ArrayList<>(ans);
    }

    public void threeSumDfs(int start, Set<List<Integer>> ans, int[] nums, List<Integer> temp) {
        if (temp.size() == 3 && temp.get(0) + temp.get(1) + temp.get(2) == 0) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (temp.size() > 1 && temp.get(0) + temp.get(1) > 0 && nums[i] > 0) {
                break;
            }

            if (temp.size() > 1 && temp.get(0) + temp.get(1) + nums[nums.length - 1] < 0) {
                break;
            }
            temp.add(nums[i]);



            threeSumDfs(i + 1, ans, nums, temp);

            temp.remove(temp.size() - 1);

        }
    }

    /**
     * 双指针+map
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        //排序
        Arrays.sort(nums);
        //用一个HashMap将所有的元素加进去，这里的keys是nums[i]，value是i
        //如果出现重复的key,那么新出现的value将会覆盖前面的一个value，我们用这个map来替代第三重循环
        HashMap<Integer, Integer> map = new HashMap<>(nums.length);
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        for(int i = 0; i < nums.length - 2; i++){
            int x = nums[i];
            //去重，假如给的用例是[0, 0, 0, 0],当i第一次遇到0时，为首次遇见没有关系，可如果这次i的循环结束了
            //i+1进入第二次循环，那么这时候还是遇到0，为连续的第二次遇见，这就造成了前后重复，必须要跳过
            if(x > 0) break;
            if(i > 0 && nums[i - 1] == nums[i]) continue;
            for(int j = i + 1; j < nums.length - 1; j++){
                int y = nums[j];
                if(x + y > 0) break;
                //去重原理同i，j必须大于i + 1，因为j是从i + 1开始的，必须要大于开始值才能后退一步
                if(j > i + 1 && nums[j - 1] == nums[j]) continue;
                //z为组合需要的那个值
                int z = 0 - x - y;
                //如果map集合里面有这个值，最重要的是要判断它的value（序号）是不是在i和j的后面
                //因为之前的第三重for循环的k是从j + 1开始的，所以它一定会大于j
                if(map.containsKey(z) && map.get(z) > j){
                    List<Integer> list = new LinkedList<>();
                    list.add(x);
                    list.add(y);
                    list.add(z);
                    results.add(list);
                }
            }
        }
        return results;
    }

    /**
     * 输入：intervals =
     * [
     * [1,3],
     * [2,6],
     * [8,10],
     * [15,18]
     * ]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     */
    public int[][] merge(int[][] intervals) {
        List<int[]> ans = new ArrayList<>();
        int start = -1;
        int end = -1;
        Arrays.sort(intervals, Comparator.comparingInt(one -> one[0]));
        for (int[] interval : intervals) {
            if (start == -1 && end == -1) {
                start = interval[0];
                end = interval[1];
            }
            if (end < interval[0]) {
                ans.add(new int[]{start, end});
                start = interval[0];
                end = interval[1];
            }
            start = Math.min(interval[0], start);
            end = Math.max(interval[1], end);
        }
        ans.add(new int[]{start, end});
        return ans.toArray(new int[ans.size()][]);
    }


    /**
     * 输入：head = [4,2,1,3]
     * 输出：[1,2,3,4]
     * 排序链表，插入排序
     */
    public ListNode sortList(ListNode head) {

        ListNode prev = new ListNode(-1);

        ListNode temp = prev;

        while (head != null) {

            while (temp.next != null && temp.next.val < head.val) {
                temp = temp.next;
            }

            ListNode tmp = head.next;
            head.next = temp.next;
            temp.next = head;
            temp = prev;

            head = tmp;
        }
        return prev.next;
    }


    /**
     * 排序链表，归并思想
     */
    public ListNode sortList2(ListNode head) {

        if (head == null) {
            return null;
        }
        ListNode ans = new ListNode();

        Deque<ListNode> nodeLists = new ArrayDeque<>();

        while (head != null && head.next != null) {
            ListNode node11 = head;
            ListNode node22 = head.next;
            ListNode temp = head.next.next;
            node11.next = null;
            node22.next = null;

            nodeLists.add(sort(node11, node22));
            head = temp;
        }
        if (head != null) {
            nodeLists.add(head);
        }

        while (!nodeLists.isEmpty()) {
            ListNode node1 = nodeLists.pollFirst();
            ListNode node2 = nodeLists.pollFirst();

            ans = merge(node1, node2);
            if (node2 == null) {
                break;
            }
            nodeLists.add(ans);
        }
        return ans;
    }


    /**
     * 两节点排序
     */
    public ListNode sort(ListNode one, ListNode two) {
        if (two == null) {
            return one;
        }
        if (one.val < two.val) {
            one.next = two;
            return one;
        } else {
            two.next = one;
            return two;
        }
    }

    /**
     * 合并有序链表
     */
    public ListNode merge(ListNode node1, ListNode node2) {
        ListNode res = new ListNode(-1);
        ListNode temp = res;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                temp.next = node2;
                node2 = node2.next;
            } else {
                temp.next = node1;
                node1 = node1.next;
            }
            temp = temp.next;
        }
        if (node1 != null) {
            temp.next = node1;
        }
        if (node2 != null) {
            temp.next = node2;
        }
        return res.next;
    }


    /**
     * 冒泡排序找到第K个大的值
     */
    public int findKthLargest(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums[nums.length - k];
    }
    /**
     * 选择排序找到第K个大的值
     */
    public int findKthLargest2(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            int max = nums[i];
            int flag = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                    flag = j;
                }
            }
            if (flag != i) {
                int temp = nums[i];
                nums[i] = nums[flag];
                nums[flag] = temp;
            }
        }
        return nums[k - 1];
    }
}
